
/*
Description:
Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"


*/

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
	string addBinary(string a, string b)
	{
		string result = "";
		int apos = a.size() - 1;
		int bpos = b.size() - 1;
		int adigit, bdigit, carry = 0;

		while (apos >= 0 || bpos >= 0 || carry == 1)
		{
			adigit = bdigit = 0;

			if (apos >= 0) adigit = a[apos--] == '1';
			if (bpos >= 0) bdigit = b[bpos--] == '1';

			// Another way: the digit is 1 if adigit + bdigit + carry == 1 or == 3, but I noticed that
			// XOR is more concise:
			result = static_cast<char>(adigit ^ bdigit ^ carry + '0') + result;
			carry = adigit + bdigit + carry >= 2;
		}

		return result;
	}

	string addBinary1(string a, string b)
	{
		string s = "";

		int c = 0, i = a.size() - 1, j = b.size() - 1;
		while (i >= 0 || j >= 0 || c == 1)
		{
			c += i >= 0 ? a[i--] - '0' : 0;
			c += j >= 0 ? b[j--] - '0' : 0;
			s = char(c % 2 + '0') + s;
			c /= 2;
		}

		return s;
	}
	string addBinary0(string a, string b) {
		string sum = "";
		int shift = 0;
		int val;
		char ca;
		char cb;

		while ((!a.empty()) && (!b.empty()))
		{
			ca = a.back();
			cb = b.back();

			val = (ca - '0') + (cb - '0') + shift;

			sum.insert(sum.begin(), val % 2 + '0');
			shift = val / 2;

			a.pop_back();
			b.pop_back();
		}

		while (!a.empty())
		{
			ca = a.back();
			val = (ca - '0') + shift;

			sum.insert(sum.begin(), val % 2 + '0');
			shift = val / 2;

			a.pop_back();
		}

		while (!b.empty())
		{
			cb = b.back();
			val = (cb - '0') + shift;

			sum.insert(sum.begin(), val % 2 + '0');
			shift = val / 2;

			b.pop_back();
		}

		if(shift != 0) sum.insert(sum.begin(), '1');
		
		return sum;
	}
};

int _addBinary()
{
	string a = "11";// "1010";
	string b = "1";// "1011";
	
	Solution solu;
	string sum;

	sum = solu.addBinary(a, b);

	cout << "a:" << a << endl;
	cout << "b:" << b << endl;
	cout << "sum:" << sum << endl;
	return 0;
}